package leetcode_800;

/**
 *@author 周杨
 *ShortestCompletingWord_748  问一个字符串数组里 哪一个字符串 是在target字符串里匹配字符最多且长度最短的
 *describe:建立映射 遍历即可 AC 60%
 *2018年10月16日 下午5:45:19
 */
public class ShortestCompletingWord_748 {
	public String shortestCompletingWord(String licensePlate, String[] words) {
        char []chars=licensePlate.toCharArray();
        int []map=new int[26];
        for(char c:chars) {
        	if(c<='Z'&&c>='A') {
        		map[c-'A']++;
        	}
        	else if(c<='z'&&c>='a')
        		map[c-'a']++;
        }
        String res=words[0];
        int count=0;
        for(String word:words) {
        	char [] wd=word.toCharArray();
        	int temp[]=new int[26];
        	int countTmp=0;
        	for(char c:wd) {
        		int diff=c-'a';
        		if(map[diff]!=0&&map[diff]-temp[diff]>0) {//原map里有映射 且值不超过原map
        			temp[diff]++;
        			++countTmp;
        		}
        	}
        	if(countTmp>count) {
        		count=countTmp;
        		res=word;
        	}
        	else if(countTmp==count) {//那么看长度
        		if(res.length()>word.length())
        			res=word;
        	}
        }
        return res;
    }
}
